The invention relates to synchronizing nodes of a multi-hop network with a Time Division Multiplex Access (TDMA) scheme, in particular a TDMA-based low-power sensor network.
In a low-power sensor network, in particular in a battery-operated wireless sensor network, it can be important to switch off the radio transceivers of the sensor nodes during their idle periods to save energy. Idle periods are time periods in which the nodes have nothing to send or to receive. A further aspect is to avoid collisions when transmitting messages or overhearing when receiving messages that are not destined to the respective node.
In such a context, TDMA-based systems are inherently energy-efficient because the nodes of the system need to turn on their radio transceiver only during their own time slots. In all other time slots, the respective node can turn off its radio transceiver. By means of an appropriate time slot assignment, it is possible to wake up senders and receivers at the same time slot so that they can exchange the messages over the network.
Many-to-one communication, as in a multi-hop network, is a very common requirement of sensor network applications, e.g. in the field of environmental monitoring or data gathering, in which the sensor nodes exchange information with a sink node generally not between themselves. In this regard, the sensor nodes generate periodic data samples and send these generated periodic data samples to the sink node for further processing. The opposite direction from the sink node to the other sensor nodes can be also used, e.g. for sending control information from the sink node to the other nodes. The routes or branches between the sink node and the further sensor nodes can build a multi-hop tree routed at the sink node and spanned over all the nodes.
In the reference N. Burri, P. von Rickenbach, R. Wattenhofer, “Dozer: Ultra-Low Power Data Gathering in Sensor Networks”, IPSN'07, Apr. 25-27, 2007, also referred to as “Dozer”, a TDMA protocol is described which is based on a local, single-hop schedule without any central or global synchronization. Each parent node in Dozer has its own schedule and can start a TDMA round with the transmission of a beacon message. Children nodes in Dozer synchronize with their parent nodes on receiving their parent's beacon. A short contention access phase follows the beacon, during which child nodes can send a connection request to the parent node. Every connected child node is assigned a time slot in the TDMA phase and uses this slot to send its data to its parent node.
Since the TDMA schedule is performed locally, collisions between nodes belonging to different schedules cannot be excluded totally. To reduce the probability for such a collision, the length of a TDMA round is extended randomly in Dozer. The respective parent node adds a random time span to each TDMA round and includes this information into the starting beacon message. As a result, its child nodes can calculate the time when the next beacon message will be sent. Dozer is mainly designed for the unidirectional transfer of data towards the sink node. Commands sent in the opposite direction are piggybacked into the beacons and, therefore, broadcasted into the whole network.
Further, in the reference I. Rhee et al., “Z-MAC: A Hybrid MAC for Wireless Sensor Networks”, IEEE/ACM Transactions on Networking, vol 16, no 3, June 2008, also referred to as “Z-MAC”, time is divided into periodic frames with a fixed number of slots. A distributed slot assignment algorithm is performed at a deployment time to assign the slots to the nodes. A node can transmit during any time slot using Carrier Sense Multiple Access (CSMA), wherein a slot's owner has a higher access priority than a non-owner. Nodes in Z-MAC can use B-MAC Low Power
In the reference V. Rajendran, J. J. Garcia-Luna-Aveces, K. Obraczka, “Energy-Efficient, Application-Aware Medium Access for Sensor Networks”, IEEE International Conference On Mobile Adhoc and Sensor Systems, November 2005, also referred to as “FLAMA”, time is divided into periods of random-access and schedule-access intervals. The random-access interval is used for time synchronization, exchanging neighbor information, and routing tree information. This interval can be long enough to cope with collisions and re-transmissions. The scheduled access interval is time-slotted. FLAMA uses a distributed election mechanism to schedule collision-free transmissions. The election algorithm is limited due to the limited resources of the sensor nodes. As a result, parent nodes have to listen to all slots to determine whether there is any transmission and can go to sleep only if they do not receive data for a certain time.
In the reference S. C. Ergen, P. Varaija, “PEDAMACS: Power Efficient and Delay Aware Medium Access Protocol for Sensor Networks”, IEEE Transactions on Mobile Computing, vol 5, no 7, July 2006, also referred to as “PEDAMACS”, time is divided into so-called phases. A phase is started by a corresponding coordination packet broadcasted by the sink node of the network. It is assumed that the broadcasted coordination packet can reach all nodes in the network, while a packet sent by a node can need multiple hops to reach the sink node. PEDAMACS operates with the following four phases described below.
The first phase is a topology-learning phase. During this topology-learning phase, the sink node floods the network with a tree construction packet, which is retransmitted by the nodes using CSMA. At the end of this topology-learning phase, all nodes should have determined their neighbors and interferers with high probability.
The second phase is a topology-collection phase. This phase follows the topology-learning phase. During this topology-collection phase, the nodes use CSMA to send their local topology information collected at the former phase to the sink. At the end of this topology-collection phase, the sink node should have the complete topology of the network.
The third phase is a scheduling phase. This scheduling phase is time-slotted. Based on the collected topology information, the sink node computes the TDMA schedule for all nodes and broadcasts this information within the coordination packet, which announces the beginning of this phase. The nodes can use the broadcasted schedule information to decide on sending, receiving, or sleeping. The schedule algorithm ensures that all data packets created in the sensor nodes reach the sink node at the end of this phase.
The fourth phase is an adjustment phase. This adjustment phase is used by the nodes to detect local topology changes. The changes are reported to the sink node by embedding the information in the data packets sent during the scheduling phase. Then, the sink node can update the routing paths or correct the schedule, if necessary.
Moreover, in the reference K. Pister, L. Doherty, “TSMP: Time Synchronized Mesh Protocol”, Proceedings IASTED International Symposium on Distributed Sensor Networks (DSN 2008), Nov. 16-18 2008, Orlando, Fla., USA, also referred to as “TSMP”, a MAC protocol of the wireless HART standard is described, which is used in industrial automation. TSMP uses a network-wide time synchronization not only to divide time into slots, but also to coordinate switching between multiple channels, in particular between multiple frequency channels.
In TSMP, time is divided into slots of 10 ms duration, wherein a slot can span over multiple channels. The result is a matrix of cells. A superframe is a collection of cells repeating at a constant rate. Events are scheduled to happen in individual cells, and the superframe length is configured in such a way that the network can support these events.
TSMP is a centralized architecture in the sense that both routing and time scheduling are performed by a central network manager and distributed to the nodes.
With regard to reference TSMP, TSMP allows two options for synchronization or sync updates. The first is a child-initiated unicast request for a time update through an acknowledgement called a keepalive. The second is a parent-initiated broadcast update, commonly known as a beacon. In a network with regular data-reporting to a time-master access point (AP), nodes close to the AP can see traffic much more often than every synchronization interval Tsync. These nodes track the AP's clock with no additional traffic when time sync information is piggybacked on top of data acknowledgements. It is the responsibility of the manager to schedule sufficient links to meet the needs of time sync.